package java19_2_18;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 基础二叉树实现
 * 使用左右孩子表示法
 */
public class MyTree {
    /**
     * 创建一个二叉树，返回根节点
     *
     * @return nodeA
     */
    public static TreeNode build() {
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');
        TreeNode nodeH = new TreeNode('H');
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.left = nodeF;
        nodeC.right = nodeG;
        nodeE.right = nodeH;
        return nodeA;
    }

    /**
     * 先序遍历：根左右
     *
     * @param root
     */
    public static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //先访问根节点
        System.out.print(root.val + " ");
        //递归访问左树
        preOrder(root.left);
        //递归访问右树
        preOrder(root.right);
    }

    /**
     * 中序遍历：左根右
     *
     * @param root
     */
    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //先递归访问左树
        inOrder(root.left);
        //然后访问根节点
        System.out.print(root.val + " ");
        //最后递归访问右树
        inOrder(root.right);
    }

    /**
     * 后序遍历：左右根
     */
    public static void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //先递归访问左树
        postOrder(root.left);
        //然后递归访问右树
        postOrder(root.right);
        //最后访问根节点
        System.out.print(root.val + " ");
    }

    /**
     * 层序遍历输出二叉树节点.用队列来解决问题
     *
     * @param root
     */
    public static void leveOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        //此时树不为空，将根节点入队
        queue.offer(root);
        while (!queue.isEmpty()) {
            //取出队首元素
            TreeNode cur = queue.poll();
            //输出队首元素的的值
            System.out.print(cur.val + " ");
            //当前节点还有子节点，将子节点从左到右依次入队
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    /**
     * 传入根节点，统计出节点个数
     *
     * @param root
     * @return 结点个数
     */
    public static int getNodes(TreeNode root) {
        //当前节点为空，边界条件
        if (root == null) {
            return 0;
        }
        //当前节点不为空，统计当前节点，然后加上左右子树节点数
        return 1 + getNodes(root.left) + getNodes(root.right);
    }

    /**
     * 传入根节点，统计叶子结点个数
     *
     * @param root
     * @return
     */
    public static int getLeafNode(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //当前为叶子结点,加一
        if (root.left == null && root.right == null) {
            return 1;
        }
        //当前树不为空，且存在子树
        return getLeafNode(root.left) + getLeafNode(root.right);
    }

    /**
     * 传入一个树和一个值，判断当前树中是否含有该元素
     *
     * @param root
     * @param val
     * @return true/false
     */
    public static boolean contains(TreeNode root, char val) {
        if (root == null) {
            return false;
        }
        //当前节点值等于所传入值
        if (root.val == val) {
            return true;
        }
        //二叉数不为空，且当前节点值不等于所传入值，在子树中继续寻找
        return contains(root.left, val) || contains(root.right, val);
    }

    /**
     * 传入一个以root为根节点的二叉树，就能求出该树的高度
     *
     * @param root
     * @return 树的高度
     */
    public static int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(height(root.left), height(root.right));
    }

    public static void main(String[] args) {
        TreeNode root = build();
        System.out.println(getNodes(root));
        System.out.println(getLeafNode(root));
        leveOrder(root);
    }

    private static class TreeNode {
        public TreeNode(char val) {
            this.val = val;
        }

        char val;
        TreeNode left;
        TreeNode right;
    }
}